package com.xdja.test;

/**
 * - 现有T个人围成一桌坐下，编号从1到T，从编号为1的人开始报数。
 * <p>
 * - 报数也从1开始，报到M的人离席，从离席者的下一位在座成员开始，继续从1开始报数。
 * <p>
 * - 求最后一个在座的成员编号。
 *
 */
public class jishengjun {

    public static void main(String[] args) {
        long before=System.currentTimeMillis();
        System.out.println(calc(10000, 3));
        long after=System.currentTimeMillis();
        System.out.println(after-before);
    }

    /**
     * 计算
     * @param t t个人
     * @param m 报数到m离席
     * @return
     */
    private static int calc(int t, int m) {
        //新建一个自定义的链表
        MyLinkedList<Integer> linkedList = new MyLinkedList<>();
        //循环添加所有人到链表里面。
        for (int i = 0; i < t; i++) {
            linkedList.add(i + 1);
        }
        //添加结束，形成闭环
        linkedList.addFinish();
        int tempCount = 1;
        //循环知道链表只剩下一个数据
        while (linkedList.size > 1) {
            //当报的数除以要离席的数字等于 要离席数字减一时；即当前报数的人，的下一个人需要离席。
            if (tempCount % m == m - 1) {
                //重置报数。由于最后又tempCount++ 操作，下个人需要报数为1。。所以重置为0
                tempCount = 0;
                //由于当前人的下一个人要离席，所以当前人的下一个人，指向要离席的人的下一个人。
                linkedList.current.next = linkedList.current.next.next;
                //链表的大小减一
                linkedList.size--;
            }
            //当前人指向下一个，做循环
            linkedList.current = linkedList.current.next;
            //报数增加1
            tempCount++;
        }
        return linkedList.current.item;
    }

    /**
     * 自定义的环形单向链表
     * @param <E>
     */
    public static class MyLinkedList<E> {
        private int size;
        //链表的最后一个节点，只在添加的时候使用
        private Node<E> last;
        //链表的首个节点,只在添加的时候使用
        private Node<E> first;
        //链表的当前节点
        private Node<E> current;

        /**
         * 添加一个数据
         * @param e
         */
        public void add(E e) {
            linkLast(e);
        }

        /**
         * 在链表的尾部添加一个新数据
         * @param e
         */
        void linkLast(E e) {
            final Node<E> l = last;
            final Node<E> newNode = new Node<>(e, null);
            last = newNode;
            if (l == null)
                first = newNode;
            else
                l.next = newNode;
            size++;
        }

        /**
         * 链表添加完成，把最后一个节点的下一个只想第一个，形成一个环。
         */
        public void addFinish() {
            last.next = first;
            current = first;
        }

        /**
         * 链表的一个节点
         * @param <E>
         */
        private static class Node<E> {
            E item;
            Node<E> next;
            Node(E element, Node<E> next) {
                this.item = element;
                this.next = next;
            }
        }

    }
}
